<head>
    <meta charset="UTF-8">
<title>算法训练 小X的暑假作业</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】<br>
小X的作业是老师给他布置的，题目很简单，求出第N个斐波那契数 mod P的值。小X怎么想也想也想不出来，只好求助于你了。<br>
【输入格式】</p>
<div>第一行为数据组数T。</div>
<div>第二行开始，以下T行，每行为老师给小X布置的作业中的N和P。</div>
<p>【输出格式】<br>
包含T行，每行是一个作业的答案。<br>
【样例输入】</p>
<div>3</div>
<div>7 3</div>
<div>1000000 89</div>
<div>987654321 30000</div>
<p>【样例输出】</p>
<div>0</div>
<div>55</div>
<div>19111</div>
<p>【数据规模和约定】</p>
<div>对于50%的数据，T&lt;=100，N&lt;=10000。</div>
<div>对于100%的数据，T&lt;=10000，N&lt;=1000000000，P&lt;=30000。</div>
<div>斐波那契数的第0个是1。</div>